package com.Algorithm;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author yisl
 * @create 2019-06-10 15:44
 */
public class ShellSort {

    /** 
    * @Description: 基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列
     * 中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
     * 1. 操作方法:
     * 选择一个增量序列 t1，t2，...，tk，其中 ti>tj，tk=1;
     * 2. 按增量序列个数 k，对序列进行 k 趟排序;
     * 3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进
     * 行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长 度。
    * @Param: [arr] 
    * @return: void 
    * @Author: yisl
    * @Date: 2019-06-10 
    */
    private void shellSort(int[] arr) {
        int dk = arr.length/2;
        while (dk >= 1){
            shellInsertSort(arr, dk);
            dk=dk/2;
        }
    }

    public synchronized void shellInsertSort(int[] arr, int k) {
        //类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了
        for (int i = k; i< arr.length; i++){
            if (arr[i] < arr[i - k]){
                int x = arr[i];
                int j;
                arr[i] = arr[i -k];
                for (j = i-k; j>=0&&x<arr[j]; j=j -k){
                    //通过循环，逐个后移一位找到要插入的位置。
                    arr[j+k]=arr[j];
                }
                //插入
                arr[j+k]=x;
            }

        }

    }

    //再写一遍
    public void shellSort3(int[] a) {
        synchronized (this) {

        }
    }

    //再写一遍
    public static void shellSort2(int[] a) {
        int dk = a.length;
        while (dk!=0){
            //步长
            dk=dk/2;
            //按组使用插入排序
            for (int i = 0; i < dk; i++){
                //对每一组做处理
                //从第二个元素开始
                for (int x = i+dk; x < a.length; x+=dk){
                    int insertVal = a[x];
                    int j = x-dk;
                    for (;j>=0&&insertVal<a[j];j-=dk){
                        a[j+dk] = a[j];
                    }
                    a[j+dk] = insertVal;
                }
            }
        }
    }

    public static void shellSort4(int[] a){
        int dk = a.length;
        while(dk!=0){
            dk = dk/2;
            for (int i=0; i<dk; i++){
                for (int j = i+dk; j < a.length ; j+=dk) {
                    int interval = a[j];
                    int x = j-dk;
                    for (; x >=0 &&interval<a[x] ; x-=dk) {
                        a[x+dk]=a[x];
                    }
                    a[x+dk] = interval;

                }
            }
        }
    }


    public static void main(String[] args) {
        int[] a= {49,38,65, 97, 76, 13, 27, 49, 55, 4};
//        ShellSort shellSort = new ShellSort();
//        shellSort.shellSort(a);
        shellSort4(a);
        System.out.println(Arrays.toString(a));
    }

}
